/* An experimental project for learning Linear List.
 * Learned from "Play with Data Structure"
 * A Linear List implemented by C array, 
 * i.e. stored in ordered storage structure.
 * 
 * * 有许多操作都要先检查线性表是否已初始化或要操作的位置i数值是否合法。这些操作
 *      封装到函数中会比较简洁，从而避免重复代码。但是鉴于只是练习，这份代码就不
 *      改了，并非我没想到 >_<
 * 
 * by Stone at 2020-3-30
 */



#include <stdio.h>
#include <stdlib.h>


#define ED "=========================\n"
#define OK 1
#define ERR 0

#define MAX_LEN 100
#define ZERO_ELEM  0    /* the zero value of ElemType */

typedef int ElemType;
typedef int Status;



struct LinearList{
    ElemType * data;
    
    int max_length;
    int length;
};


/* Prerequisite:
 *    * List is existed.
 *    * List is not initialized.
 *
 * Result: Apply memory for elements and set the other variables.
 */
Status initList(struct LinearList *ls, int length){
    if (length >= MAX_LEN){
        printf("init: over MAX_LEN\n");
        return ERR;
    }
   
   /* test if the list is already initialized. */
   if (ls->max_length != 0){  
        printf("init: the list is already initialized.\n");
        return ERR;
    }

    ls->max_length = length;
    
    printf("init: pointer of data(before) -> %p\n", ls->data);
    ls->data = (ElemType *)malloc(length * sizeof(ElemType));
    printf("init: pointer of data(after)  -> %p\n", ls->data);

    return OK;
}


/* Prerequisite: The LinearList is initialized and not freed before.
 * Result: the memory of list is freed and set the other members to 0.
 */
Status deleteList(struct LinearList *ls){
    /* test if the list could be deleted */
    if (ls->max_length == 0 || ls->data==0){
        printf("Cannot delete a list which not initialized(whose max_length is 0 or data is NULL).\n");
    }
    free(ls->data);
    ls->data = NULL;
    ls->max_length = 0;
    ls->length = 0;
    printf("List deleted\n");
}


/* Prerequisite: List is avaiable and initialized.
 * Result: return the length of List.
 */
int getLength(struct LinearList *ls){
    return ls->length;
}


/* Prerequisite: List is existed; 0 <= i < length; 
 * Result: Return the element at position i if possible.
 */
Status getElem(struct LinearList *ls, int i){
    if (i<0 || i>=getLength(ls)){
        printf("getElem: invaild position i: %i\n", i);
        return ERR;
    }
    
    return ls->data[i];
}


/* Prerequisite: Initialized list; Spare room in the list for the new element. 
 * Result: Append an element at the end of the list(if success), or do nothing
 * (if no spare room left).
 */
Status pushElem(struct LinearList *ls, ElemType e){
    if (ls->max_length == 0 || ls->data==NULL){
        printf("pushElem: The list is not initialized.\n");
        
        return ERR;
    }
    else if (ls->max_length <= ls->length){
        printf("pushElem: The list if full, cannot push new element.\n");

        return ERR;
    }

    /* do the push */
    ls->data[ls->length] = e;
    ls->length += 1;

    return OK;
}


/* Prerequisite: The list contains at least one element. 
 * Result: Pop one element from the tail of list.
 */
Status popElem(struct LinearList *ls){
    if (ls->length == 0){
        printf("popElem: cannot pop, the list is empty.\n");

        return ERR;
    }

    /* do the pop */
    ls->data = ZERO_ELEM;  // not necessary
    ls->length -= 1;

    return OK;
}


/* Prerequisite:
 *      * The list is initialized.
 *      * The position is available: 0 <= i <= list.length;
 *      * There is sapre room for new element.
 * Result: Insert an element at position i, and move the following 
 *      elements backwards.
 */
Status insertElem(struct LinearList *ls, int i, ElemType e){
    if (ls->max_length == 0 || ls->data == NULL){
        printf("insertElem: list uninitialized.\n");

        return ERR;
    }
    else if(i < 0 || i > ls->length){
        printf("insertElem: invaild position i: %i\n", i);

        return ERR;
    }
    else if(ls->length +1 > ls->max_length){
        printf("insertElem: the list is full\n");

        return ERR;
    }

    /* do the insertion */
    /* move the elements */
    int j = 0;
    for (j = ls->length -1; j>=i; j--){
        ls->data[j+1] = ls->data[j];
    }

    /* insert the element */
    ls->data[i] = e;
    ls->length += 1;

    return OK;
}


/* Prerequisite:
 *      * The list contains at least one element.
 *      * 0 <= i < length
 * Result: Delete the element at position i, and 
 *      move the following elements forward.
 */
Status removeElem(struct LinearList *ls, int i){
    if (ls->length == 0 || ls->data == NULL){
        printf("remove: list uninitialized.\n");
        return ERR;
    }
    else if (i<0 || i >= ls->length){
        printf("remove: unvalid position i: %i\n", i);
        return ERR;
    }


    /* do the remove */
    if (i <= ls->length -1){
        /* If i indicates the last element, then nothing need to be move.
         * Ohterwise, move the elements after i. */
        int j = 0;
        int end_idx = ls->length -1;
        for (j=i; j < end_idx; j++){
            ls->data[j] = ls->data[j+1];
        }
        
    }
    
    ls->length -= 1;
    return OK;
}


/* To test the functions of LinearList */
void testInitAndDelete(struct LinearList *ls) {
    
    printf("\n\n==testInitAndDelete %s\n", ED);
    
    printf("init length 10\n");
    initList(ls, 10);
    printf("deleting...\n");
    deleteList(ls);
    printf("init length MAX_LEN + 1\n");
    initList(ls, MAX_LEN + 1);

    printf(ED);
}


void test_push_get_pop(struct LinearList *ls){
    printf("\n\ntest_push_get_pop %s\n", ED);
    int num = 5;
    
    initList(ls, num);
    printf("list initlized, length: %i, max_length: %i\n", ls->length, ls->max_length);
    
    printf("pushing...\n");
    int i = 0;
    for (i=0; i<num; i++){
        pushElem(ls, i);
        printf("pushed %i\n", i);
    }

    printf("push one more.\n");
    pushElem(ls, 100);

    printf("\ngetting...\n");
    for (i=0; i<num; i++){
        printf("got: %i\n", getElem(ls, i));
    }

    printf("get more than max_length\n");
    getElem(ls, ls->length +1);    
    
    printf("\npoping...\n");
    for (i=0; i<num; i++){
        popElem(ls);
    }
    printf("pop one more\n");
    popElem(ls);

    deleteList(ls);  //do the clearing
    printf(ED);
}


void test_insert_and_remove(struct LinearList *ls){
    printf("\n\ntest_insert_and_remove %s\n", ED);

    int num = 5;
    initList(ls, num);
    printf("list initilized: length:%i, max_length: %i\n", ls->length, ls->max_length);
    
    printf("\ninserting...\n");
    int i = 0;
    for (i=0; i<num; i++){
        insertElem(ls, i, i);
        printf("insert: %i\n", i);
    }

    printf("insert one more\n");
    insertElem(ls, ++i, ++i);
    printf("insert at i < 0\n");
    insertElem(ls, -1, 0);

    
    printf("\tremove at invalid position\n");
    removeElem(ls, ls->length);
    printf("\tremove at less than 0\n");
    removeElem(ls, -1);
    printf("\nremoving...\n");
    for (i=0; i<num; i++){
        printf("%i th remove\n", i);
        removeElem(ls, 0);
    }


    deleteList(ls);
    printf(ED);
}


int main(){
    struct LinearList ls = {0};
    
    testInitAndDelete(&ls);
    test_push_get_pop(&ls);
    test_insert_and_remove(&ls);

    printf("\n\nLiearList  done.\n");

    return 0;
}
















